#ifndef __DECISION_TREE__
#define __DECISION_TREE__

/*
 * DecisionTree :
 *     Models generic Bases classes to solve any Decision Tree based problem.
 *     It helps the designer to model the right classes which will allow to solve
 *     the problem effectively. Also Each classes defines the effective virtual
 *     functions which allows the user to stress upon the smallest possible subproblem
 *     effectively(i..e implementation of virtual function in derived classes).
 *     The actual implementation of decsion tree is also done in the base classes.
 */

#include <vector>
#include <set>
#include <iterator>

class Model ;
class Item ;
class State ;
class Constraint ;
class DecisionTree ;

typedef std::vector<State*> Solution ;
typedef void (*solutionCallback)(Solution& soln) ;

// Helper functor to model collection of Items in a set.
struct ltItem
{
    bool operator()(const Item* p_item1, const Item* p_item2) const
    {
        return ((size_t)p_item1 < (size_t)p_item2) ; 
    }
} ;

enum ConstraintType
{
    PRE_CONSTRAINT = 0 ,
    POST_CONSTRAINT
} ;

class InvalidGoalException
{
    public :
        InvalidGoalException() {}
        ~InvalidGoalException() {}

        virtual const char* what() const throw() ; 
   private :
} ;

class Model
{
    public :
        Model() {}
        virtual ~Model() {}    
        virtual bool        operator==(const Model& model) const = 0 ;
        // It should do the basic initialization of the model
        virtual Model*      getNewModelWithSelfTraits() const = 0 ;

        virtual void        printModel() const { return ; }
    protected :
    private :
} ;

class Item
{
    public :
        Item() {}
        virtual ~Item() {}

        // This perturb function should remember when was it called for the first time
        // and should iterate till further perturbation is not possible. In case of
        // Pentominoes, the moment the item reached back at R0. It should merely return false.
        virtual bool        perturb() { return false ; }
    protected :
    private :
} ;

class State
{
    public :
        // As it needs to populate the Child States of the current state.
        // Only DecisionTree has complete knowledge of the depth(in terms of
        // Decision Tree) to explore the child states.
        friend class DecisionTree ;

        // For those Decision Tree Models which is not modelled in terms of Item...
        State() : m_pItem(NULL), m_childStates(), m_itr(NULL), m_curIdx(0) {}
	State(Item* p_item) : m_pItem(p_item), m_childStates(), m_itr(NULL), m_curIdx(0) {}
        virtual ~State() ;
        //{
        //    delete m_pItem ;
        //    Need to call delete for each child state.
        //}

        virtual void        initiateStateForSolution() { return ;} 
        virtual bool        fixStateForSolution() { return true ; } 
        virtual void        resetStateOriginal()  { return ; }
        virtual bool        applyStateOnModel(Model* p_model) const = 0 ;
        virtual bool        backtrackState(Model* p_model) const = 0 ;

        // Would be handy in printing final solution. Also overload cout to print
        // the State.
        virtual void        printState() const = 0 ;
        size_t              numChildStates() const { return m_childStates.size() ; }

        void                initializeChildStateIterator(bool allChildStatesGenerated) ;
        State*              getNextChildState() ;

        Item*               getContainedItem() const { return m_pItem ; }
        //Only those states will be added which satisfies constraints...
        void                addChildState(State* p_state) { m_childStates.push_back(p_state) ; }

    protected :
        // Each State need to clearly specify as to whats its contribution if any to the
        // final solution, as in 8 queens a state needs to store the location where the
        // Queen is placed.
        Item*               m_pItem ; // Might not be needed for all DecisionTree problem.
                                      // Also the actual owner of the Item is DecisionTree class.
        std::vector<State*> m_childStates ;

        std::vector<State*>::iterator m_itr ;
        int                 m_curIdx ;


        // For Pentominoes the State class also need to store the index at which
        // the item is placed.
    private :
        // This will perturb the current state by changing the state of the item.
        // As in pentominoes, it will rotate/flip the pentominoe till it lands itself
        // in a valid position which satisfies the constraints, if no such state is
        // found, it will return false.        
        bool                perturb() ;
        void                deleteChildStates() ;
} ;

// Constraint would just tell whether the current state(Different from State class)
// of the Model is valid 
class Constraint
{
    public :
        Constraint(const std::string& name, 
		   ConstraintType type = PRE_CONSTRAINT, 
		   bool active = true) : m_constraintName(name), m_constraintType(type),
                                         m_activeConstraint(active) 
        {
        }
        virtual ~Constraint() {}

        // A state will only be applied on the model if the constraints are satisfied.
        virtual bool        isSatisfied(const Model* p_curModel, const Model* p_goalModel, 
					const State* p_toState) const = 0 ;

	std::string         getConstraintName() const { return m_constraintName ; }
        bool                isActiveConstraint() const { return m_activeConstraint ; }
        void                setConstraintActive(bool status) { m_activeConstraint = status ; }

        ConstraintType      getConstraintType() const { return m_constraintType ; }
    private :
    protected :
	std::string         m_constraintName ;
        ConstraintType      m_constraintType ;
        bool                m_activeConstraint ;
} ;

class DecisionTree
{
    public :
        DecisionTree() : m_pModel(NULL), m_pGoalModel(NULL),
                         m_pStateZero(NULL), m_constraints(), m_items()
        {
        }
        virtual ~DecisionTree() ;
        
        // Generates all possible child states at one shot.
        virtual size_t      generateAllChildStates(const Solution& curState, State* p_state) const = 0 ;
        // Generates child states one by one, when no more child states generation is possible
        // it returns NULL.
        virtual size_t      generateNextChildState(const State* p_prevSiblingState,
						   const Solution& states,
						   State* p_parentState) const = 0 ;
        virtual bool        isFinalStateReached() const { return (*m_pModel == *m_pGoalModel) ; }

        // If we are trying to reach to the state p_toState from whatever is the current state
        // Will we be able to satisfy all the constraints.
        bool                willConstraintsBeSatisfied(const Model* p_curModel, 
						       const Model* p_goalModel,
						       const State* p_toState) const ;   // For Pre Constraints...
	bool                areConstraintsSatisfied(const Model* p_curModel, 
						    const Model* p_goalModel,
						    const State* p_toState) const ; // For Post Constraints.

        // The following functions are recursive functions....
	bool                getASolution(Solution& states, bool genStatesTogether = true) const ;
	bool                getAllSolutions(solutionCallback cb, bool genStatesTogether=true) const ;

        void                setGoalModel(Model* p_model) ;
        void                addConstraint(Constraint* p_cons) { m_constraints.push_back(p_cons) ; }
        Constraint*         getConstraint(const std::string& name) const ;
        void                getActiveConstraints(std::vector<Constraint*>& constraints) const ;

	virtual std::string getCurSolutionStateStr(const Solution& states) const { return "" ; }

    protected :
        // Should Build the Decison Tree, It should also build stateZero.
        virtual bool        initializeModel() ;
        void                resetTree() ;

        virtual bool        buildStateZero() = 0 ;
        virtual void        initializeItems() = 0 ;
        virtual void        buildConstraints() = 0 ;
        
        Model*              m_pModel ;     // Will get altered by applying on state.
        Model*              m_pGoalModel ; // This is the state where we are intending to reach, Decision
                                           // Tree is not the owner of goalModel, as it is set by the user
                                           // externally, the user needs to delete it.
        State*              m_pStateZero ; // This is dummy State which does not contain
                                           // any item but is a driver for solution
                                           // generation.
        std::vector<Constraint*> m_constraints ;

        // Items to play with should also be stored in derived class. As in
        // Pentominoes we need it but not in 8 queens.
        std::set<Item*>  m_items ;         // Could be empty        
        
        // The final State to which the decision tree has to reach to should
        // be stored by Concrete DecisionTree class, as in some case(s) a concrete
        // final model is needed(as in Pentominoes) whereas in other either such
        // specific final state not known but merely a notio as to how would it
        // look like(as in 8 queens problem)
    private :
        bool                buildASolution   (Solution& states, State* p_childState,
                                              bool genStatesTogether) const ;
        bool                buildAllSolutions(Solution& states,
                                              State* p_state, solutionCallback cb,
                                              bool& solnFound,
                                              bool genStatesTogether) const ; 
} ;

#endif
